package 简单.模拟;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
 * 每次「迁移」操作将会引发下述活动：
 * 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
 * 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
 * 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
 * 请你返回 k 次迁移操作后最终得到的 二维网格。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shift-2d-grid
 */
public class 二维网格迁移_1260 {

    public static void main(String[] args) {

        int[][] grid = {{1}, {2}, {3}, {4}, {7}, {6}, {5}};
        System.out.println(shiftGrid(grid, 23));

    }

    /**
     * 找规律
     * 每迁移一次，每个元素向右移动一位，超出边界，向下，
     * 最右下角的一个元素，移动到最左上角
     * 使用队列模拟
     * 将表格依次入队列，每迁移一次，只需要将队尾一个元素移动到队首
     *
     * @param grid
     * @param k
     * @return
     */
    public static List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> lists = new ArrayList<>();
        k %= grid.length * grid[0].length;
        Deque<Integer> queue = new ArrayDeque<>();

        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                queue.addLast(grid[row][column]);
            }
        }

        while (k-- > 0) {
            queue.addFirst(queue.pollLast());
        }

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < grid[0].length; i++) {
                list.add(queue.pollFirst());
            }
            lists.add(list);
        }
        return lists;
    }
}
